package com.xhj.joffer.aa;
import org.junit.Test;
import org.springframework.util.StringUtils;

import java.util.HashMap;
/**
 * 题目: 0到n-1, 每次删去第m个数, 接着从下一个开始计数, 直到剩余一个, 求这个数.
 * @author haijianxia pure_xhj@163.com
 * @Date 2021-09-19
 * @Time 21:54
 */
public class FindTheLastOne {
  public static void main(String[] args) {
	  DoubleLinkedNode c1=new DoubleLinkedNode(0);
	  c1.next(new DoubleLinkedNode(1))
		  .next(new DoubleLinkedNode(2))
		  .next(new DoubleLinkedNode(3))
		  .next(new DoubleLinkedNode(4))
		  .next(new DoubleLinkedNode(5))
		  .next(new DoubleLinkedNode(6))
		  .next(new DoubleLinkedNode(7))
		  .next(c1);
    System.out.println("c1.toString() = " + c1.toString());
	  int result = test01(4, 2);
    System.out.println("result = " + result);

	  System.out.println("==========================70866==========================");
	  int result2 = test01(866, 922);
	  System.out.println("result2 = " + result2);
  }
  /** 思路一: 模拟整个过程 */
  @Test
  public static int test01(int n, int m) {
  	System.out.println("\n=============test01==============");
  	System.out.println("思路一: 模拟整个过程");
  	long time01 = System.currentTimeMillis();

	  if(n<1 || m<1){
		  throw new NullPointerException("无意义的入参");
	  }

	  int result =0;
	  DoubleLinkedNode nodes = new DoubleLinkedNode(0).getUntil(n);
//    System.out.println(nodes.toString());

	  // 设立一个startNow
	  // 设立一个length
	  // 节点删除
	  // length==1, return
	  DoubleLinkedNode startNow=null;
	  int length=n;

	  startNow=nodes;
	  while(length>=1){
		  if (length == 1) {
			  result=startNow.val;
			  break;
		  }
		  int times=0;
		  for (int i = 0; i < m; i++) {
	      if (i == m-1) {
		      //节点删除
		      startNow.prev.next=startNow.next;
		      startNow.next.prev=startNow.prev;
		      length--;
		      // 更新当前节点, 准备开始下次的循环计数
		      startNow=startNow.next;
          //		      System.out.println("startNow.toString() = " + startNow.toString());
		      continue;
	      }
			  // 往下数
			  startNow=startNow.next;
			  char[] chars = String.valueOf(++times).toCharArray();
			  char[] format= new char[]{'0','0','0','0','0','0','0','0','0','0'};
        for (int i1 = 0; i1 < chars.length; i1++) {
          format[10-1-i1]=chars[chars.length-1-i1];
        }
			  System.out.println(String.valueOf(format));
		  }
	  }


  	long time0101  = System.currentTimeMillis() - time01;
  	System.out.println("test01 耗时 =  " + time0101  + "ms");
  	System.out.println("=================================");

  	return result;
  }

  /** 思路二: 数组模拟, 下标计算 */
  @Test
  public static int test02(int n, int m) {
  	System.out.println("\n=============test02==============");
  	System.out.println("思路二: 数组模拟, 下标计算");
  	long time02 = System.currentTimeMillis();

	  if (n<1 || m<1) {
		  throw new NullPointerException("入参不合法");
	  }
	  int result = 0;
	  int[] tempArrayNow=new int[n];

	  while(tempArrayNow.length>=1){
      if (tempArrayNow.length == 1) {
        result=tempArrayNow[0];
        break;
      }

		  // 计算m, 删除
	  	tempArrayNow=new int[--n];
      for (int i = 0; i < tempArrayNow.length; i++) {
        if (m <= tempArrayNow.length) {
          if (i == m) {
	          continue;
          }

        }//m>length
        else{

        }
      }
	  }

  	long time0202  = System.currentTimeMillis() - time02;
  	System.out.println("test02 耗时 =  " + time0202  + "ms");
  	System.out.println("=================================");

  	return result;
  }


  private static class DoubleLinkedNode {
  	int val;
  	DoubleLinkedNode prev;
  	DoubleLinkedNode next;
	  public DoubleLinkedNode(int val) {
		  this.val = val;
	  }
	  DoubleLinkedNode next(DoubleLinkedNode last){
	  	this.next=last;
	  	last.prev=this;
	  	return this.next;
	  }
	  DoubleLinkedNode getUntil(int n){
		  DoubleLinkedNode result = new DoubleLinkedNode(0);
		  DoubleLinkedNode temp = result;
		  for (int i = 0; i< n-1; i++) {
			  DoubleLinkedNode next = new DoubleLinkedNode(i + 1);
			  temp.next=next;
			  next.prev=temp;
        if (i == n-1-1) {
          result.prev=next;
          next.next=result;
        }
			  // 更新当前指针
			  temp=temp.next;
      }
	  	return result;
	  }
	  /**
	   * 防止循环链表
	   * @return
	   */
	  @Override
	  public String toString(){
		  int length=1;
		  String str=""+this.val;
		  HashMap<DoubleLinkedNode, Integer> hashMap = new HashMap();
		  hashMap.put(this,1);
		  DoubleLinkedNode nodeNow=this.next;
		  while(nodeNow!=null && !hashMap.containsKey(nodeNow)){
		  	str+=(" --> "+nodeNow.val);
			  hashMap.put(nodeNow,1);
			  nodeNow=nodeNow.next;
			  length++;
		  }
		  return "("+length+") : "+str;
	  }

  }
}
